# 暴力超时
# class Solution(object):
#     def orderOfLargestPlusSign(self, n, mines):
#         """
#         :type n: int
#         :type mines: List[List[int]]
#         :rtype: int
#         """
#         mines = {(mine[0], mine[1]) for mine in mines}
#         max_len = 0
#         for i in range(n):
#             for j in range(n):
#                 if (i, j) not in mines:
#                     step = 0
#                     while True:
#                         step += 1
#                         count = 0
#                         for ux, uy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
#                             if 0 <= i + ux * step < n and 0 <= j + uy * step < n and (i + ux * step, j + uy * step) not in mines:
#                                 count += 1
#                             else:
#                                 break
#                         if count < 4:
#                             break
#                     max_len = max(max_len, step)
#         return max_len

class Solution(object):
    def orderOfLargestPlusSign(self, n, mines):
        """
        :type n: int
        :type mines: List[List[int]]
        :rtype: int
        """
        mines = {(mine[0], mine[1]) for mine in mines}
        DP1 = [[0 for _ in range(n)] for _ in range(n)]
        DP2 = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            left = 0
            right = 0
            while right < n:
                if (i, right) in mines:
                    if right - left != 0:
                        for j in range(left, right):
                            DP1[i][j] = min(j + 1 - left, right - j)
                    left = right + 1
                right += 1
            if right - left != 0:
                for j in range(left, right):
                    DP1[i][j] = min(j + 1 - left, right - j)
        for j in range(n):
            left = 0
            right = 0
            while right < n:
                if (right, j) in mines:
                    if right - left != 0:
                        for i in range(left, right):
                            DP2[i][j] = min(i + 1 - left, right - i)
                    left = right + 1
                right += 1
            if right - left != 0:
                for i in range(left, right):
                    DP2[i][j] = min(i + 1 - left, right - i)
        max_len = 0
        for i in range(n):
            for j in range(n):
                max_len = max(max_len, min(DP1[i][j], DP2[i][j]))
        return max_len

data = Solution()
n = 5
mines = [[4, 2]]
print(data.orderOfLargestPlusSign(n, mines))
